package dp;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 剑指 Offer II 101. 分割等和子串
 */
public class P101 {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) {
            return false;
        }
        sum /= 2;
        //return backTrack(nums, 0, 0, sum);
        return dp(nums, sum);
    }

    /**
     * @param nums
     * @param idx     当前访问的位置
     * @param currNum 当前的总和，不包含位置idx
     * @param target  需要比较的终值
     * @return
     */
    boolean backTrack(int[] nums, int idx, int currNum, int target) {
        if (nums[idx] + currNum == target || currNum == target) {
            return true;
        } else if (idx + 1 < nums.length) {
            boolean flag1 = backTrack(nums, idx + 1, currNum + nums[idx], target);
            boolean flag2 = backTrack(nums, idx + 1, currNum, target);
            if (flag1 || flag2) {
                return true;
            }
        }
        return false;
    }


    boolean dp(int[] nums, int target) {
        Set<Integer> result = new HashSet<>();
        result.add(0);
        for (int num : nums) {
            Set<Integer> tmpSet = new HashSet<>(result);
            for (Integer n : tmpSet) {
                if (n + num == target) {
                    return true;
                } else if (n + num < target) {
                    tmpSet.add(n + num);
                }
            }
            result=tmpSet;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 3, 3, 4, 5};
        System.out.println(new P101().canPartition(nums));
    }

}
